class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& a) {
        sort(a.begin(), a.end());
        int n = a.size();
        vector<vector<int>>ans;
        for (int i = 0; i < n - 2;) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int x = a[i] + a[l] + a[r];
                if (x > 0)r--;
                else if (x < 0)l++;
                else {
                    ans.push_back({ a[i],a[l],a[r] });
                    l++, r--;
                    while (l < r && a[l] == a[l - 1])l++;
                    while (l < r && a[r] == a[r + 1])r--;
                }
            }
            i++;
            while (i < n && a[i] == a[i - 1])i++;
        }
        return ans;
    }
};